package main

import "fmt"

func quickSort(data []int) {
	sortWithinScope(data, 0, len(data)-1)
}

// 在指定范围内排序
func sortWithinScope(data []int, start int, end int) {
	if start < end {
		pivot := part(data, start, end)
		sortWithinScope(data, start, pivot-1)
		sortWithinScope(data, pivot+1, end)
	}
}

// 将指定范围内的数据分成大小两列，返回中间参考值的位置
func part(data []int, start int, end int) int {
	ref := data[end]
	nextLowerIndex := start
	for i := start; i < end; i++ {
		if data[i] < ref {
			data[nextLowerIndex], data[i] = data[i], data[nextLowerIndex]
			nextLowerIndex++
		}
	}
	data[nextLowerIndex], data[end] = data[end], data[nextLowerIndex]
	return nextLowerIndex
}

func main() {
	a := []int{10, 1, 2, 3, 9, 4, 5, 6, 7, 0}
	sortWithinScope(a, 0, len(a)-1)
	fmt.Println(a)
}
